
/**
 * @param <T> Generic type
 * @author Lukas Koell
 * @author David Medenjak
 * @author Johannes Riedmann
 */
public class TreeIterator<T> implements TreeIter<T> {

    /** represents the Nodes in order of the BFS */
    private LinkedItem<Node<T>> flattenedTree;
    /** subtree we are iterating through */
    protected Tree<T> tree;
    /** root Node of subtree */
    private Node<T> root;
    /** true if it's first call of next, else false */
    private boolean isFirstElement;

    /**
     * Constructor
     * @param tree Tree we want to iterate.
     */
    public TreeIterator(Tree<T> tree) {
        this.tree = tree;
        root = tree.getRoot();
        isFirstElement = true;  //needs to be set for next call
        flattenTree();
        return;
    }

    /**
     * Constructor
     * @param node Start node of iteration.
     */
    public TreeIterator(Node<T> node) {
        root = node;
        isFirstElement = true;  //needs to be set for next call
        flattenTree();
        return;
    }

    /**
     * Makes a linked list to parse through.
     */
    private void flattenTree() {
        if (getRoot() == null) {     //if root is null return null
            return;
        } else if (getRoot() != null && //if root != null, but child nodes are null return root
                getRoot().getLeftChild() == null && getRoot().getRightChild() == null) {
            setFlattenedTree(new LinkedItem<Node<T>>(getRoot()));
            return;
        } else {    //else iterate through subtree
            flattenImplementation();

            while (getFlattenedTree().getPrevious() != null) {    //set LinkedItem<T> to first item
                setFlattenedTree(getFlattenedTree().getPrevious());
            }
        }
    }

    /**
     * Implementation of how to link the list. (Preorder, inorder, ...)
     */
    protected void flattenImplementation() {
        Queue<Node<T>> q = new Queue<Node<T>>();
        q.push(getRoot());    //add root of subtree to the queue
        setFlattenedTree(new LinkedItem<Node<T>>(getRoot()));  //initiate List with root

        Node<T> currentNode = null;

        while (!q.isEmpty()) {
            currentNode = q.pop();      //get first item out of queue

            if (currentNode.getLeftChild() != null) {
                //if so, add node to queue and to flattenedTree
                q.push(currentNode.getLeftChild());
                LinkedItem<Node<T>> newItem = new LinkedItem<Node<T>>(currentNode.getLeftChild());
                getFlattenedTree().setNext(newItem);
                getFlattenedTree().getNext().setPrevious(getFlattenedTree());
                setFlattenedTree(getFlattenedTree().getNext());
            }
            if (currentNode.getRightChild() != null) {
                LinkedItem<Node<T>> newItem = new LinkedItem<Node<T>>(currentNode.getRightChild());
                q.push(currentNode.getRightChild());
                getFlattenedTree().setNext(newItem);
                getFlattenedTree().getNext().setPrevious(getFlattenedTree());
                setFlattenedTree(getFlattenedTree().getNext());
            }
        }
    }

    /**
     * Adds an item as next to flattenedTree.
     * @param node Item to add.
     */
    protected final void setNextItem(Node<T> node) {
        if (node == null) {
            return;
        }
        if (getFlattenedTree() == null) {
            setFlattenedTree(new LinkedItem<Node<T>>(node));
            return;
        }
        LinkedItem<Node<T>> newItem = new LinkedItem<Node<T>>(node);
        newItem.setPrevious(getFlattenedTree());
        getFlattenedTree().setNext(newItem);
        setFlattenedTree(getFlattenedTree().getNext());
    }

    /**
     * @return boolean if there is a next item in the LinkedItem<T> or not
     */
    @Override
    public boolean hasNext() {
        if (getFlattenedTree() == null) {
            return false;
        }
        return getFlattenedTree().getNext() != null;
    }

    /**
     * @return boolean if there is a previous item in the LinkedItem<T> or not
     */
    @Override
    public boolean hasPrevious() {
        return getFlattenedTree().getPrevious() != null;
    }

    /**
     * @return next value of current flattened tree
     */
    @Override
    public T next() {
        if (!isFirstElement) {
            setFlattenedTree(getFlattenedTree().getNext());
            return getFlattenedTree().getValue().getValue();
        }
        isFirstElement = false;
        return getFlattenedTree().getValue().getValue();
    }

    /**
     * @return previous value of current flattened tree
     */
    @Override
    public T previous() {
        setFlattenedTree(getFlattenedTree().getPrevious());
        //root auf vorheriges element setzen
        return getFlattenedTree().getValue().getValue();
    }

    /**
     * uses breadth-first search to create an iterator for a subtree
     * @return TreeIterator<T> which contains the nodes of the subtree in BFS order
     */
    @Override
    public TreeIterator<T> down() {
        return new TreeIterator<T>(getFlattenedTree().getValue());
    }

    /**
     * @return the flattenedTree
     */
    public LinkedItem<Node<T>> getFlattenedTree() {
        return flattenedTree;
    }

    /**
     * @param flattenedTree the flattenedTree to set
     */
    public void setFlattenedTree(LinkedItem<Node<T>> flattenedTree) {
        this.flattenedTree = flattenedTree;
    }

    /**
     * @return the root
     */
    public Node<T> getRoot() {
        return root;
    }

    /**
     * @param root the root to set
     */
    public void setRoot(Node<T> root) {
        this.root = root;
    }
}
